//
// Source code recreated from a .class file by IntelliJ IDEA
// (powered by FernFlower decompiler)
//

package 力扣.题库.二分查找;

import java.util.Arrays;

public class demo_2300 {
    public demo_2300() {
    }

    public static void main(String[] args) {
        int[] spells = new int[]{15, 37, 15, 32, 4, 27, 20, 24, 12, 26, 39, 32, 39, 20, 19, 22, 33, 2, 22, 9, 18, 12, 5};
        int[] potions = new int[]{31, 40, 29, 19, 27, 16, 25, 8, 33, 25, 36, 21, 7, 27, 40, 24, 18, 26, 32, 25, 22, 21, 38, 22, 37, 34, 15, 36, 21, 22, 37, 14, 31, 20, 36, 27, 28, 32, 21, 26, 33, 37, 27, 39, 19, 36, 20, 23, 25, 39, 40};
        long success = 600L;
        int[] successful = successfulPairs(spells, potions, success);
        System.out.println(Arrays.toString(successful));
    }

    public static int[] successfulPairs(int[] spells, int[] potions, long success) {
        Arrays.sort(potions);
        int[] out = new int[spells.length];

        for(int i = 0; i < spells.length; ++i) {
            int spell = spells[i];
            int l = 0;
            int r = potions.length - 1;

            while(l <= r) {
                int mid = l + (r - l) / 2;
                long n = (long)potions[mid] * (long)spell;
                if (n < success) {
                    l = mid + 1;
                } else {
                    r = mid - 1;
                }
            }

            if (l == potions.length) {
                out[i] = 0;
            } else {
                out[i] = potions.length - l;
            }
        }

        return out;
    }
}
